package lex.expression;

/**
 * ��׺���ʽת��Ϊ��׺���ʽ�Ĳ��裺<br>
 * 1����ʼ��һ���ն�ջ��������ַ�����ÿա� 
 * 2�������Ҷ�����׺���ʽ��ÿ��һ���ַ� 
 * 3������ַ��ǲ���������ӵ�����ַ� 
 * 4������ַ��Ǹ�����������pop��������ֱ���������ţ�opening parenthesis�������ȼ��ϵ͵Ĳ�����
 *   ����ͬһ���ȼ����ҽ�Ϸ�š������������ѹ�루push����ջ�� 
 * 5������ַ��Ǹ������ţ�����ѹ���ջ�� 
 * 6������ַ��Ǹ������ţ�closing parenthesis��������������ǰ���������в�����Ȼ���������ӵ����
 *   �ַ� 
 * 7�����������ַ��ĩβ���������в�������ӵ�����ַ� 
 */
import java.util.Collections;
import java.util.Stack;

public class Parser {
	private Lexer lexer = null;
	private Token lastToken = null;

	public PostfixExpression parse(String expr) {
		if (null == this.lexer)
			this.lexer = new Lexer(expr);
		else
			this.lexer.setSource(expr);
		this.lastToken = null;
		// ===============================
		Token token = null;
		Stack<Element> postfix = new Stack<Element>();
		Stack<Operator> stack = new Stack<Operator>();
		while (true) {
			token = lexer.nextToken();
			if (TokenType.END == token.getTokenType()) {
				while (false == stack.empty())
					postfix.push(stack.pop());
				Collections.reverse(postfix);
				return new PostfixExpression(postfix);
			}
			TokenType type = token.getTokenType();
			if (true == token.isOperator()) {
				if (TokenType.ADD == type || TokenType.SUBTRACT == type) {
					if (null == lastToken || TokenType.LEFT_P == lastToken.getTokenType()) {
						type = (type == TokenType.ADD ? TokenType.POSITIVE : TokenType.NEGATE);
						token = new Token(type, token.getImage());
					}
				}
				// operator
				switch (type) {
				case LEFT_P:
					stack.push(new Operator(token));
					break;
				case RIGHT_P:
					while (false == stack.empty()) {
						Operator peek = stack.peek();
						if (peek.getTokenType() == TokenType.LEFT_P) {
							stack.pop();
							break;
						}
						postfix.push(stack.pop());
					}
					break;
				default:
					Operator op = new Operator(token);
					while (false == stack.empty()) {
						Operator peek = stack.peek();
						if (peek.getTokenType() == TokenType.LEFT_P || peek.getPriority() < op.getPriority())
							break;
						postfix.push(stack.pop());
					}
					stack.push(op);
				}
			} else if (true == token.isOperand()) {
				postfix.push(new Operand(token.getImage()));
			}
			this.lastToken = token;
		}
	}
}
